package com.cb2.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/linked-list-frequency'>链表频率(Linked List Frequency)</a>
 * <p>给定包含 k 个 不同 元素的链表的 head 节点，创建一个长度为 k 的链表，以 任何顺序 返回链表中所有 不同元素 出现的 频率。</p>
 * <p>返回这个链表的头节点。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1:
 *      输入：head = [1,1,2,1,2,3]
 *      输出：[3,2,1]
 *      解释：列表中有 3 个不同的元素。1 的频率是 3，2 的频率是 2，3 的频率是 1。因此，我们返回 3 -> 2 -> 1。
 *      注意 1 -> 2 -> 3，1 -> 3 -> 2，2 -> 1 -> 3，2 -> 3 -> 1，和 3 -> 1 -> 2 都是合法的答案。
 *
 *  示例 2:
 *      输入：head = [1,1,2,2,2]
 *      输出：[2,3]
 *      解释：列表中有 2 个不同的元素。1 和 2 出现的频率是 2 和 3。因此，我们返回 2 -> 3。
 *
 *  示例 3:
 *      输入：head = [6,5,4,3,2,1]
 *      输出：[1,1,1,1,1,1]
 *      解释：列表中有 6 个不同的元素。每个元素的频率是 1。因此，我们返回 1 -> 1 -> 1 -> 1 -> 1 -> 1。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中的节点数字范围在 [1, 10^5]之间。</li>
 *     <li>1 <= Node.val <= 10^5</li>
 *     <li></li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/8 14:35
 */
public class LC3063LinkedListFrequency_S {
    static class Solution {
        public ListNode frequenciesOfElements(ListNode head) {
            Map<Integer, Integer> cnt = new HashMap<>();
            while (head != null) {
                cnt.merge(head.val, 1, Integer::sum);
                head = head.next;
            }
            ListNode dummyHead = new ListNode(-1);
            for (Integer c : cnt.values()) {
                dummyHead.next = new ListNode(c);
            }
            return dummyHead.next;
        }

        public ListNode frequenciesOfElements2(ListNode head) {
            int[] cnt = new int[10 ^ 5 + 1];
            while (head != null) {
                cnt[head.val]++;
                head = head.next;
            }
            ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            for (int c : cnt) {
                if (c != 0) {
                    currNode.next = new ListNode(c);
                    currNode = currNode.next;
                }
            }
            return dummyHead.next;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(1);
        head1.next.next = new ListNode(2);
        head1.next.next.next = new ListNode(1);
        head1.next.next.next.next = new ListNode(2);
        head1.next.next.next.next.next = new ListNode(3);

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(1);
        head2.next.next = new ListNode(2);
        head2.next.next.next = new ListNode(2);
        head2.next.next.next.next = new ListNode(2);

        ListNode head3 = new ListNode(6);
        head3.next = new ListNode(5);
        head3.next.next = new ListNode(4);
        head3.next.next.next = new ListNode(3);
        head3.next.next.next.next = new ListNode(2);
        head3.next.next.next.next.next = new ListNode(1);

        Solution solution = new Solution();
        Printer.printListNode(solution.frequenciesOfElements(head1));
        Printer.printListNode(solution.frequenciesOfElements(head2));
        Printer.printListNode(solution.frequenciesOfElements(head3));
    }

}
